Write a function:

def solution(N)

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5.

Assume that:

    N is an integer within the range [1..2,147,483,647].

Complexity:

    expected worst-case time complexity is O(log(N));
    expected worst-case space complexity is O(1).

Analyzing number of bits



In [1]:

    
n = 1

print n.bit_length()

a = n.bit_length()

print bin(n)

print '%0*d' % (a, int(bin(n)[2:]))

print '{0:08b}'.format(n)

n = 10



In [2]:

    
n = 10

print n.bit_length()

a = n.bit_length()

print bin(n)

print '%0*d' % (a, int(bin(n)[2:]))

print '{0:08b}'.format(n)

n=100



In [3]:

    
n = 10

print n.bit_length()

a = n.bit_length()

print bin(n)

print '%0*d' % (a, int(bin(n)[2:]))

print '{0:08b}'.format(n)

converting binary to decimal



In [13]:

    
n = 157


count_one = 0
count_gap = 0
binarygap = 0

for count in xrange(n.bit_length()):
    print count
    
    if n % 2:
        count_one +=1
        n = n /2
    elif count_one == 1:
        count_gap += 1
        print "count gap: ", count_gap
        n = n / 2
    
    if count_one > 1:
        if binarygap < count_gap:
            binarygap = count_gap
            print "binary gap", binarygap
        count_one = 1
        count_gap = 0

print binarygap









    



0
1
count gap:  1
2
binary gap 1
3
4
5
count gap:  1
6
count gap:  2
7
binary gap 2
2



In [10]:

    
157 /2









    Out[10]:





78



In [12]:

    
78/2









    Out[12]:





39

testing more binary to decimal conversions



In [26]:

    
n = 37


count_one = 0
count_gap = 0
binarygap = 0

for count in xrange(n.bit_length()):
    print count
    print "n", n
    
    if n % 2:
        count_one +=1
        n = n /2
    elif count_one == 1:
        count_gap += 1
        print "count gap: ", count_gap
        n = n / 2
    
    if count_one > 1:
        if binarygap < count_gap:
            binarygap = count_gap
            print "binary gap", binarygap
        count_one = 1
        count_gap = 0

print binarygap









    



0
n 37
1
n 18
count gap:  1
2
n 9
binary gap 1
3
n 4
count gap:  1
4
n 2
count gap:  2
5
n 1
binary gap 2
2



In [29]:

    
n = 142


count_one = 0
count_gap = 0
binarygap = 0

for count in xrange(n.bit_length()):
    print count
    print "n", n
    
    if n % 2:
        count_one +=1
        n = n /2
    elif count_one == 1:
        count_gap += 1
        print "count gap: ", count_gap
        n = n / 2
    else:
        n = n/2
    
    if count_one > 1:
        if binarygap < count_gap:
            binarygap = count_gap
            print "binary gap", binarygap
        count_one = 1
        count_gap = 0

print binarygap









    



0
n 142
1
n 71
2
n 35
3
n 17
4
n 8
count gap:  1
5
n 4
count gap:  2
6
n 2
count gap:  3
7
n 1
binary gap 3
3



In [20]:

    
142 / 2









    Out[20]:





71



In [22]:

    
71/2









    Out[22]:





35



In [24]:

    
35/2









    Out[24]:





17



In [31]:

    
n = 488


count_one = 0
count_gap = 0
binarygap = 0

for count in xrange(n.bit_length()):
    print count
    print "n", n
    
    if n % 2:
        count_one +=1
        n = n /2
    elif count_one == 1:
        count_gap += 1
        print "count gap: ", count_gap
        n = n / 2
    else:
        n = n/2
    
    if count_one > 1:
        if binarygap < count_gap:
            binarygap = count_gap
            print "binary gap", binarygap
        count_one = 1
        count_gap = 0

print binarygap









    



0
n 488
1
n 244
2
n 122
3
n 61
4
n 30
count gap:  1
5
n 15
binary gap 1
6
n 7
7
n 3
8
n 1
1



In [33]:

    
n = 181


count_one = 0
count_gap = 0
binarygap = 0

for count in xrange(n.bit_length()):
    print count
    print "n", n
    
    if n % 2:
        count_one +=1
        n = n /2
    elif count_one == 1:
        count_gap += 1
        print "count gap: ", count_gap
        n = n / 2
    else:
        n = n/2
    
    if count_one > 1:
        if binarygap < count_gap:
            binarygap = count_gap
            print "binary gap", binarygap
        count_one = 1
        count_gap = 0

print binarygap









    



0
n 181
1
n 90
count gap:  1
2
n 45
binary gap 1
3
n 22
count gap:  1
4
n 11
5
n 5
6
n 2
count gap:  1
7
n 1
1



In [35]:

    
def solution(N):
    
    count_one = 0
    count_gap = 0
    binarygap = 0
    
    for count in xrange(N.bit_length()):   
        if N % 2:
            count_one +=1
            
            N = N /2
        
        elif count_one == 1:
            count_gap += 1
            
            N = N / 2
        
        else:
            N = N/2
        
        if count_one > 1:
            if binarygap < count_gap:
                binarygap = count_gap
                
            count_one = 1
            
            count_gap = 0
    
    return binarygap



In [37]:

    
print solution(181)

[result:] https://codility.com/demo/results/trainingJUFAAF-QJM/



In [ ]: